import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Partition {
    int size;
    boolean isAllocated;

    public Partition(int size) {
        this.size = size;
        this.isAllocated = false;
    }
}

class MemoryManager {
    ArrayList<Partition> partitions;
    PrintWriter output;

    public MemoryManager(PrintWriter output) {
        partitions = new ArrayList<>();
        this.output = output;
    }

    public void addPartition(int size) {
        partitions.add(new Partition(size));
    }

    public void bestFitAllocate(int requestSize) {
        int bestIndex = -1;
        int bestSize = Integer.MAX_VALUE;

        for (int i = 0; i < partitions.size(); i++) {
            Partition partition = partitions.get(i);
            if (!partition.isAllocated && partition.size >= requestSize) {
                if (partition.size < bestSize) {
                    bestSize = partition.size;
                    bestIndex = i;
                }
            }
        }
        if (bestIndex != -1) {
            partitions.get(bestIndex).isAllocated = true;
            output.println("Allocated " + requestSize + " bytes to partition " + bestIndex);
        } else {
            output.println("Allocation failed for " + requestSize);
        }
    }

    public void freePartition(int index) {
        if (index >= 0 && index < partitions.size()) {
            partitions.get(index).isAllocated = false;
            output.println("Freed partition " + index);
        } else {
            output.println("Invalid partition index");
        }
    }

    private void mergePartition() {
        ArrayList<Partition> mergedPartitions = new ArrayList<>();
        int i = 0;

        while (i < partitions.size()) {
            if (!partitions.get(i).isAllocated) {
                int size = 0;
                while (i < partitions.size() && !partitions.get(i).isAllocated) {
                    size += partitions.get(i).size;
                    i++;
                }
                mergedPartitions.add(new Partition(size));
            } else {
                mergedPartitions.add(partitions.get(i));
                i++;
            }
        }
        partitions = mergedPartitions;
    }

    public void displayMemory() {
        output.println("Memory Partitions:");
        for (int i = 0; i < partitions.size(); i++) {
            Partition partition = partitions.get(i);
            String status = partition.isAllocated ? "Allocated" : "Free";
            output.println("Partition " + i + ": Size=" + partition.size + ", Status=" + status);
        }
    }
}

class PageTable {
    int[] table;
    PrintWriter output;

    public PageTable(int size, PrintWriter output) {
        table = new int[size];
        for (int i = 0; i < size; i++) {
            table[i] = -1;
        }
        this.output = output;
    }

    public void setMapping(int virtualPage, int physicalPage) {
        table[virtualPage] = physicalPage;
    }

    public int getPhysicalAddress(int virtualAddress) {
        int pageSize = 4096;
        int virtualPage = virtualAddress / pageSize;
        int offset = virtualAddress % pageSize;
        int physicalPage = table[virtualPage];

        if (physicalPage == -1) {
            output.println("Page fault");
            return -1;
        }
        return physicalPage * pageSize + offset;
    }
}

class PageReplacement {
    int numFrames;
    Queue<Integer> frames;
    int pageFaults;
    PrintWriter output;

    public PageReplacement(int numFrames, PrintWriter output) {
        this.numFrames = numFrames;
        this.frames = new LinkedList<>();
        this.pageFaults = 0;
        this.output = output;
    }

    public void requestPage(int page) {
        if (!frames.contains(page)) {
            if (frames.size() < numFrames) {
                frames.add(page);
            } else {
                int replacedPage = frames.poll();
                frames.add(page);
                output.println("Page " + replacedPage + " replaced with " + page);
            }
            pageFaults++;
        } else {
            output.println("Page " + page + " already in memory");
        }
    }

    public void report() {
        output.println("Total page faults: " + pageFaults);
        output.println("Current frames: " + frames);
    }
}

public class Memory {
    public static void main(String[] args) {
        try (BufferedReader input = new BufferedReader(new FileReader("input.txt"));
             PrintWriter output = new PrintWriter(new FileWriter("output.txt"))) {

            // 动态分区分配
            MemoryManager memoryManager = new MemoryManager(output);
            String line;
            while ((line = input.readLine()) != null) {
                if (line.startsWith("addPartition")) {
                    int size = Integer.parseInt(line.split(" ")[1]);
                    memoryManager.addPartition(size);
                } else if (line.startsWith("bestFitAllocate")) {
                    int requestSize = Integer.parseInt(line.split(" ")[1]);
                    memoryManager.bestFitAllocate(requestSize);
                } else if (line.startsWith("freePartition")) {
                    int index = Integer.parseInt(line.split(" ")[1]);
                    memoryManager.freePartition(index);
                } else if (line.startsWith("displayMemory")) {
                    memoryManager.displayMemory();
                }
            }

            // 分页地址变换
            output.println("\n--- Page Table ---");
            PageTable pageTable = new PageTable(10, output);
            pageTable.setMapping(0, 5);  // Virtual page 0 maps to Physical page 5
            pageTable.setMapping(1, 3);  // Virtual page 1 maps to Physical page 3

            int virtualAddress = 8192;  // Example virtual address
            int physicalAddress = pageTable.getPhysicalAddress(virtualAddress);
            if (physicalAddress != -1) {
                output.println("Physical address for virtual address " + virtualAddress + ": " + physicalAddress);
            }

            // 页面置换算法 (FIFO)
            output.println("\n--- Page Replacement (FIFO) ---");
            PageReplacement pageReplacement = new PageReplacement(3, output);
            int[] pageRequests = {1, 2, 3, 1, 4, 2, 5};

            for (int page : pageRequests) {
                pageReplacement.requestPage(page);
            }

            pageReplacement.report();

        } catch (IOException e) {
            e.printStackTrace();
        }
    }
}
